Lab 23

1. Write a complete C++ program that does the following:
• Complete the insertion sort function in the Lab 23 PowerPoint.
• Write a main function that passes an unsorted array of integers to the insertion sort function.
• You may either manually initialize the array to integer values or you may populate it with random values using the rand function, your choice.
• After passing the array to insertion sort, print the elements of the array to the monitor to confirm that they are now in sorted order.
Example main function that uses insertionSort:

int main() { int cap = 10; int nums[cap]; fillArray(nums, cap); // fill array with random numbers printArray(nums, cap); // print array insertionSort(nums, cap); // sort elements in array printArray(nums, cap); // print sorted array return 0; }

Sample run of program:

89 16 58 15 93 36 55 33 12 24 12 15 16 24 33 36 55 58 89 93
2. Write a complete C++ program that does the following:
• Declares a 1D int array with capacity 10.
• Uses a function called readInput that takes the 1D array and an integer capacity as input. The function and reads values into the array from the user.
• Passes the filled array and its capacity to another function called arrayAverage that computes and returns the average of all elements in the array.
• The return value is stored in a double variable called average.
• Print the average to the monitor.
• The main function then passes the 1D array, its capacity and the average to a third function called greaterThanAverage that prints all elements in the array that are greater than the average.
Example main function that uses these functions:

int main() { int nums[10]; double average; cout << "Enter ten numbers:\n"; // read in numbers from user readInput(nums, 10); // compute average of elements in array average = arrayAverage(nums, 10); // print average value to monitor cout << average << endl; // print array elemnets that are greater than average greaterThanAverage(nums, 10, average); return 0; }

Sample run of program>

Enter ten numbers: 4 1 7 3 8 4 6 9 2 1 4.5 7 8 6 9
3. Eight queens are to be placed on an 8 x 8 chessboard in such a way that one queen is to be placed in each row. Write a complete C++ program that does the following:
• Declare an array queenColumns[] with capacity 8 to represent such a configuration.
• If queenColumns[r] has value c then in row r there is a queen in column c.
• Pass the array and its capacity to a function called readInput that reads in values into the array.
• The program then passes array queenColumns to a function called printBoard that prints a 2D board with . in the non-queen columns of each row and Q in the queen column of each row.
Example main function that uses these functions:

int main() { int queenColumns[8]; cout << "Enter columns for queens:\n"; readInput(queenColumns, 8); printBoard(queenColumns, 8); return 0; }

Sample run of program:

Enter columns for queens: 3 7 1 6 2 5 4 6 ...Q.... .......Q .Q...... ......Q. ..Q..... .....Q.. ....Q... ......Q.
4. (Similar to the problem above, but the user specifies a row for each column instead of a column for each row.) Eight queens are to be placed on a 8 x 8 chessboard in such a way that one queen is to be placed in each column. Write a complete C++ program that does the following:
• Declare an array queenRows[] with capacity 8 to represent such a configuration.
• If queenRows[c] has value r then in column c there is a queen in row r.
• The program should ask the user to enter the row that contains queens in the 8 rows.
• The program then passes array queenRows to a function called printBoard that prints a 2D board with . in the non-queen row of each row and Q in the queen row of each column.
Example main function that uses these functions:

int main() { int queenRows[8]; cout << "Enter rows for queens:\n"; readInput(queenRows, 8); printBoard(queenRows, 8); return 0; }

Sample run of program:

Enter rows for queens: 6 2 4 7 1 0 3 5 .....Q.. ....Q... .Q...... ......Q. ..Q..... .......Q Q....... ...Q....
5. Write a complete C++ program that does the following:
• Declares an array of integers with capacity 20.
• Passes the array to a function called fillWithDistinctNums that takes a 1D array and an integer capacity as input. The function fills the array with random integers between 1 and 20 (inclusive) BUT each number must be different than all previous entries in the array. In other words, no number can appear more than once in the array.
• Generate the entries as random numbers and repeatedly make new numbers until a legal entry is found
• HINT: You will need to use a while loop inside the for loop. For each new number generated, you will check all previous entries in the array to see if the new number is a duplicate of a previous number already in the array.
• Passes the filled array to a function called printArray that takes the 1D array and its capacity as input and prints all elements in the array separated by a space.
Example main function that uses fillWithDistinctNums:

int main() { int nums[20]; fillWithDistinctNums(nums, 20); printArray(nums, 20); return 0; }

Sample run of program. Notice that no number is repeated:

4 20 9 3 1 12 7 16 11 19 8 18 15 2 13 5 14 6 10 17

Another sample run of program:

6 15 14 17 3 13 16 5 12 10 2 8 4 18 19 9 11 1 7 20

For a more concrete set of hints to solve this problem, here is an outline of the code needed for fillWithDistinctNumbers:

fillWithDistinctNums (int nums[], int cap): // need srand to guarantee distinct sequence of random numbers for each run srand(time(0)); for loop to access all elements of input array at index i: declare bool variable numOK and initialize to false while !numOK: set nums[i] = random number between 1 and 20 set numOK equal to true // need to loop through existing array entries (all entries to left of current index) // to see if new num is a duplicate of any of them for loop checking indices 0 through i - 1 (int j = 0; j < i; j++): // check if nums[i] == nums[j] // if this is true, the new number is not OK if nums[i] == nums[j] set numOK = false